package puzzle.projecteuler;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

import astudy.util.AdvMath;

/**
 *  a + b*sqrt(d)
 * ---------------, d is not square
 *        c
 * @author Administrator
 *
 */
public class QuadricFraction {

	int a;
	int b;
	int c;
	int d;
	
	public static QuadricFraction ZERO = new QuadricFraction(0,0,1,0);
	
	public QuadricFraction(QuadricFraction f) {
		this.a = f.a;
		this.b = f.b;
		this.c = f.c;
		this.d = f.d;
	}
	
	public QuadricFraction(int a, int b, int c, int d) {
		if (d < 0) {
			throw new RuntimeException("Wrong Action!");
		} else if (d > 0) {
			int t = (int)Math.sqrt(d);
			if (t*t == d) {
				throw new RuntimeException("Wrong Action!");
			}
		}
		if (c == 0) {
			throw new RuntimeException("Wrong Action!");
		}
		this.a = a;
		this.b = b;
		this.c = c;
		this.d = d;
	}
	@Override
	public String toString() {
		return "[" + a + ((b<0)?"-":"+") + Math.abs(b) + "*sqrt(" + d + ")]/" + c; 
	}

	@Override
	public boolean equals(Object o) {
		if (o == null || !(o instanceof QuadricFraction)) {
			return false;
		} else {
			QuadricFraction f = (QuadricFraction)o;
			return this.a == f.a && this.b == f.b && this.c == f.c && this.d == f.d;
		}
	}
	
	private QuadricFraction regular() {
		
		int t = AdvMath.gcd(AdvMath.gcd(BigInteger.valueOf(this.a), BigInteger.valueOf(this.b)), BigInteger.valueOf(this.c)).intValue();
		if (this.c < 0) {
			t = -t;
		}
		if (t != 0) {
			this.a /= t;
			this.b /= t;
			this.c /= t;
		}
		return this;
	}
	
	public QuadricFraction sub(QuadricFraction f) {
		if (f.d != this.d && f.d != 0) {
			throw new RuntimeException("Wrong Action!");
		} else {
			if (f.d == 0) {
				f.c = 0;
				f.d = d;
			}
			int x = this.a*f.c - f.a*this.c;
			int y = this.b*f.c - f.b*this.c;
			int z = f.c*this.c;
			return new QuadricFraction(x, y, z, d).regular();
		}
	}
	
	public QuadricFraction add(QuadricFraction f) {
		if (f.d != this.d && f.d != 0) {
			throw new RuntimeException("Wrong Action!");
		} else {
			if (f.d == 0) {
				f.c = 0;
				f.d = d;
			}
			int x = this.a*f.c + f.a*this.c;
			int y = this.b*f.c + f.b*this.c;
			int z = f.c*this.c;
			return new QuadricFraction(x, y, z, d).regular();
		}
	}
	
	public QuadricFraction mul(QuadricFraction f) {
		if (f.d != this.d && f.d != 0) {
			throw new RuntimeException("Wrong Action!");
		} else {
			if (f.d == 0) {
				f.c = 0;
				f.d = d;
			}
			int x = this.a*f.a + f.b*this.b*this.d;
			int y = this.a*f.b + f.a*this.b;
			int z = f.c*this.c;
			return new QuadricFraction(x, y, z, d).regular();			
		}
	}

	public QuadricFraction div(QuadricFraction f) {
		if (f.d != this.d && f.d != 0) {
			throw new RuntimeException("Wrong Action!");
		} else if (f.a == 0 && f.b == 0) {
			throw new RuntimeException("Wrong Action!");
		} else {
			if (f.d == 0) {
				f.c = 1;
				f.d = d;
			}
			int x = (this.a*f.a - this.b*f.b*this.d)*f.c;
			int y = (this.b*f.a - this.a*f.b)*f.c;
			int z = this.c*(f.a*f.a - f.b*f.b*this.d);
			return new QuadricFraction(x, y, z, d).regular();
		}
	}
	
	public double doubleValue() {
		
		return (this.a + this.b * Math.sqrt(this.d))/this.c;
	}
	
	public ContinuedFraction continuedFractionValue() {
		
		List<Integer> tmp = new ArrayList<Integer>();
		List<QuadricFraction> remainder = new ArrayList<QuadricFraction>();
		
		QuadricFraction f = null;
		QuadricFraction r = null;
		int t = 0;
		
		QuadricFraction one = new QuadricFraction(1,0,1,this.d);
		f = new QuadricFraction(this);
		t = (int)Math.floor(f.doubleValue());
		tmp.add(t);
		r = f.sub(new QuadricFraction(t,0,1,d));
		remainder.add(r);
//		System.out.println(t + "\t" + r);

		int n = 0;
		while (true) {
			f = one.div(r);
			t = (int)Math.floor(f.doubleValue());
			r = f.sub(new QuadricFraction(t,0,1,d));
			if ((n = remainder.indexOf(r)) > -1) {
				tmp.add(t);
				remainder.add(r);
//				System.out.println(t + "\t" + r);
				break;
			} else {
				tmp.add(t);
				remainder.add(r);
//				System.out.println(t + "\t" + r);
			}
		}
		//return
		n ++;
		Integer[] a = tmp.toArray(new Integer[tmp.size()]);
		Integer[] pre = new Integer[n];
		System.arraycopy(a, 0, pre, 0, pre.length);
		Integer[] repeated = new Integer[tmp.size()-n];
		System.arraycopy(a, n, repeated, 0, repeated.length);
		return new ContinuedFraction(pre, repeated);
	}
}
